package org.usmile.algorithms.leetcode.hard;

import java.util.Arrays;
import java.util.HashSet;
import java.util.Set;

/**
 * 41. 缺失的第一个正数
 *
 * 给你一个未排序的整数数组 nums ，请你找出其中没有出现的最小的正整数。
 * 请你实现时间复杂度为 O(n) 并且只使用常数级别额外空间的解决方案。
 *
 * 示例 1：
 * 输入：nums = [1,2,0]
 *
 * 输出：3
 *
 * 示例 2：
 * 输入：nums = [3,4,-1,1]
 * 输出：2
 *
 * 示例 3：
 * 输入：nums = [7,8,9,11,12]
 * 输出：1
 *
 * 提示：
 * 1 <= nums.length <= 5 * 105
 * -231 <= nums[i] <= 231 - 1
 * 通过次数268,399提交次数626,680
 */
public class _0041 {
}


// 以数组索引标识已出现的正数
class _0041_Solution {
    public int firstMissingPositive(int[] nums) {
        // 1. 将小于 0 的元素变成正数
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] <= 0) {
                nums[i] = nums.length + 1;
            }
        }

        // 2. 将索引为 nums[i] 的元素设置为负数
        for (int i = 0; i < nums.length; i++) {
            int num = Math.abs(nums[i]);
            if (num <= nums.length) {
                nums[num - 1] = -Math.abs(nums[num - 1]);
            }
        }

        // 3. 找到第一个大于 0 的元素，返回这个元素对应的下标 i 再加 1
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] > 0) {
                return i + 1;
            }
        }

        return nums.length + 1;
    }
}

class _0041_Solution1 {
    public int firstMissingPositive(int[] nums) {
        Set<Integer> set = new HashSet<>();
        for (int num : nums) {
            set.add(num);
        }

        for (int i = 1; i <= nums.length; i++) {
            // 哈希查找
            if (!set.contains(i)) {
                return i;
            }
        }

        return nums.length + 1;
    }
}

// 排序解法
class _0041_Solution2 {
    public int firstMissingPositive(int[] nums) {
        Arrays.sort(nums);
        int i = 0;
        while (i < nums.length && nums[i] <= 0) {
            i++;
        }
        if (i == nums.length || nums[i] != 1) {
            return 1;
        }

        i++;
        while (i < nums.length
                && (nums[i - 1] == nums[i] || nums[i - 1] + 1 == nums[i])) {
            i++;
        }

        return nums[i - 1] + 1;
    }
}